package com.peng.old.sort;

import java.util.Arrays;

/**
 * 计数排序
 */
public class CountSort {

    public static void main(String[] args) {
        int[] arr = new int[]{43,50,46,50,30,31,33,32,41};
//        int[] arr = new int[]{3,6,1,6,8,8,8};
        int[] sort = sort(arr, 30, 50);

        System.out.println(Arrays.toString(sort));

    }

    /**
     *  @param arr
     * @param minBound 数据最小值（包含）
     * @param maxBound 数据最大值（包含）
     * @return
     */
    public static int[] sort(int[] arr, int minBound, int maxBound){
        for (int i : arr) {
            if(i<minBound || i>maxBound){
                System.err.println("不符合范围的值："+i);
                return arr;
            }
        }
        int range = maxBound - minBound+1;
        int[] resultArr = new int[arr.length];

        int[] countBucketArr = new int[range];//存放范围 的计数桶

        //计数桶对每个出现的数的次数进行统计
        for (int i = 0; i < arr.length; i++) {
            countBucketArr[arr[i]-minBound]++;
        }

        //累加数组，保证稳定性
        for (int i = 1; i < countBucketArr.length; i++) {
            countBucketArr[i] = countBucketArr[i]+countBucketArr[i-1];
        }

        //倒着遍历数组，依据每个数最后一次出现的索引值 通过递减而达到稳定性的效果。
        for (int i = arr.length - 1; i >= 0; i--) {
            resultArr[--countBucketArr[arr[i]-minBound]] = arr[i];
        }

        return resultArr;

    }

}
